package main.Q301_400;

import java.util.*;

public class Q311_320 {
    public static void main(String[] args) {
        System.out.println("Question311：");
        System.out.println("Question312：戳气球");
        System.out.println("Question313：超级丑数");
        System.out.println("Question314：");
        System.out.println("Question315：计算右侧小于当前元素的个数");
        System.out.println("Question316：");
        System.out.println("Question317：");
        System.out.println("Question318：最大单词长度乘积");
        System.out.println("Question319：灯泡开关");
        System.out.println("Question320：");
    }
}

class Question312{
    public int maxCoins(int[] nums) {
        int length=nums.length;
        int[][] dp=new int[length+2][length+2];
        int[] val=new int[length+2];
        val[0]=1;
        val[length+1]=1;
        for (int i=1;i<=length;i++) val[i]=nums[i-1];
        for (int i=length-1;i>=0;i--) {
            for (int j=i+2;j<=length+1;j++){
                for (int k=i+1;k<j;k++){
                    int sum=val[i]*val[j]*val[k];
                    sum+=dp[i][k]+dp[k][j];
                    dp[i][j]=Math.max(dp[i][j],sum);
                }
            }
        }
        return dp[0][length+1];
    }
}

class Question313{
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] power=new int[primes.length];
        long[] dp=new long[n];
        dp[0]=1;
        for (int i=1;i<n;i++){
            long min=Long.MAX_VALUE;
            for (int j=0;j<power.length;j++) {
                min=Math.min((long) min,dp[power[j]]*primes[j]);
            }
            dp[i]=min;
            for (int j=0;j< primes.length;j++) {
                if (min==dp[power[j]]*primes[j]) power[j]++;
            }
        }
        return (int)dp[n-1];
    }
}

class Question315{
    public List<Integer> countSmaller(int[] nums) {
        TreeMap<Integer,Integer> map=new TreeMap<>();
        List<Integer> result=new ArrayList<>();
        for (int i=nums.length-1;i>=0;i--) {
        }
        Collections.reverse(result);
        return result;
    }
}

class Question318{
    public boolean isValid(Set<Character> s1,Set<Character> s2){
        for (Character c:s1){
            if (s2.contains(c)) return false;
        }
        return true;
    }
    public int maxProduct(String[] words) {
        int max=0;
        List<Set<Character>> list=new ArrayList<>();
        for (String s:words){
            char[] str=s.toCharArray();
            Set<Character> set=new HashSet<>();
            for (int i=0;i< str.length;i++){
                if (!set.contains(str[i])) set.add(str[i]);
            }
            list.add(set);
        }
        for (int i=0;i< words.length;i++){
            for (int j=i+1;j< words.length;j++){
                int length=0;
                if (isValid(list.get(i),list.get(j))){
                    length=words[i].length()* words[j].length();
                }
                max=Math.max(length,max);
            }
        }
        return max;
    }
}

class Question319{
    public int bulbSwitch(int n) {//第i盏灯在第i+1轮后状态不变，第i盏灯经历偶数次变化时亮奇数次变化时灭
        return (int)Math.sqrt(n);
    }
}